package 动态规划;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class No120三角形最小路径和 {

    /**
     * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
     * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
     *
     * 例如，给定三角形：
     * [
     *      [2],
     *     [3,4],
     *    [6,5,7],
     *   [4,1,8,3]
     * ]
     * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
     *
     * 说明：
     * 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
     */

    Integer[][] memo;

    /**
     * 仅仅是递归+记忆法(自顶向下),下面再来个动态规划法(自底向上~~~)
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        //浪费点空间是必要的
        this.memo=new Integer[triangle.size()][triangle.size()];
        return dfs(triangle,0,0);
    }

    private int dfs(List<List<Integer>> triangle,int level,int index){
        if(level==triangle.size()){
            return 0;
        }
        //index+1必定不越界,因为下一层一定会多一个
        if(memo[level][index]==null) {
            memo[level][index] = triangle.get(level).get(index)
                    + Math.min(dfs(triangle, level + 1, index), dfs(triangle, level + 1, index + 1));
        }
        return memo[level][index];
    }

    public int minimumTotalDbGood(List<List<Integer>> triangle) {
        //为何要加1?使最后一层可以加上0
        int[][] db=new int[triangle.size()+1][triangle.size()+1];
        /**
         * 自底向上
         */
        for (int i = triangle.size()-1; i >=0 ; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                /**
                 * 从最底层开始往上加
                 */
                db[i][j]=triangle.get(i).get(j)+Math.min(db[i+1][j],db[i+1][j+1]);
            }
        }
        //到了0层下面只有两个元素可以吸取,吸取最小的加上自身就是答案
        return db[0][0];
    }

    public static void main(String[] args) {
        List<List> lists = JSON.parseArray("[[2],[3,4],[6,5,7],[4,1,8,3]]", List.class);
        No120三角形最小路径和 n=new No120三角形最小路径和();
    }


}
